package dp_package.p01;

/**
 * 474. 一和零
 * 输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
 * 输出：4
 * 解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
 * 其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。
 *
 * @author luolidong
 * @version 1.0
 * @create 2021-08-05 09:52
 */
public class L474 {

    public int findMaxForm(String[] strs, int m, int n) {
        if (strs.length == 0) return 0;
        //1.确定dp数组含义：dp[i][j]代表最多i个0，j个1的最大个数
        //相当于i,j都是背包重量，str本身是价值
        int[][] dp = new int[m + 1][n + 1];
        //2.初始化
        //3.确定转移方程
        for (String str : strs) {
            //1的个数
            int one = 0;
            int zero = 0;
            for (int i = 0; i < str.length(); i++) {
                if (str.charAt(i) == '1') one++;
                else zero++;
            }
        //4.遍历顺序,相当于一维背包，背包重量需要倒序
            for (int i = m;i<=zero;i--) {
                for (int j = n;j<=one;j--) {
                    dp[i][j]=Math.max(dp[i][j], dp[i-zero][j-one]+1);
                }
            }
        }
        return dp[m][n];
    }

    public static void main(String[] args) {
        L474 l474 = new L474();
        int maxForm = l474.findMaxForm(new String[]{"10", "0001", "111001", "1", "0"}, 5, 3);
        System.out.println(maxForm);
    }
}
